<?php

/*
 * Find the longest palindrome substring (abccbccba) of a string.
 *
 * Algo:
 * asdbasdklakweklnblkalskdjioflqkwe
 *     <-j   i   k->
 *
 * Create palindrome length count = array_fill(0, string.lenght, 0);
 *
 * while( i < string.length ) {
 * 		even = false;
 * 		j=i-1, k=i+1;
 * 		if( string[i+1] == string[i] ){
 * 			even = true;
 * 			k = i + 2;
 * 			count[i] = count[i+1] = 1;
 * 		}
 * 		while( string[j] == string[k] ){
 * 			j--, k++;
 * 			count[ i ]++;
 * 			if( even ){
 * 				count[ i+1 ]++;
 * 			}
 * 		}
 *
 * 		if( even ){
 * 			i += 2;
 * 		}
 * 		else {
 * 			i++;
 * 		}
 * }
 *
 * Largest count[i] value gives the longest palindrome position and
 * i * 2 (even) or i * 2 + 1 (odd) gives the palindrome substring length
 *
 */

$string = "The string asdf fdsa contains a palindrome substring.";
//$string = 'abcba';

echo "$string<br/>";
longestPalindromeSubstring($string);

function longestPalindromeSubstring( $string ){
	$length = strlen($string);
	if( 1 >= $length ){
		echo "Whole string is palindrome.";
		return true;
	}

	if( 2 == $length ){
		if( $string[0] == $string[1] ){
			echo "Whole string is palindrome.";
			return true;
		}
	}

	$count = array_fill(0, $length, 0);

	//
	$longest = 0;
	$position = 0;
	$i = 0;
	while( $i < $length - 1 ) {
 		$even = false;
 		$j = $i - 1;
 		$k = $i + 1;

 		if( $string[$i+1] == $string[$i] ){
  			$even = true;
  			$k = $i + 2;
  			$count[$i] = 1;
  			$count[$i+1] = 1;
  		}

  		while( $j >= 0 && $k < $length && $string[$j] == $string[$k] ){
  			$j--;
  			$k++;
  			$count[ $i ]++;
  			if( $even ){
  				$count[ $i+1 ]++;
  			}
  		}

		if( $longest < $count[ $i ] ){
  			$longest = $count[ $i ];
  			$position = $i;
  		}

  		if( $even ){
  			$i += 2;
  		}
  		else {
  			$i++;
  		}
	}

	var_dump( $count );

	if( $longest > 0 ){
		echo "Longest palindrome substring is at $position<br/>";
		if( $count[$position] == $count[$position+1] ){
			// even
			echo substr($string, $position-$count[$position]+1, $count[$position] * 2);
		}
		else {
			// odd
			echo substr($string, $position-$count[$position], $count[$position] * 2 + 1);
		}
		return true;
	}
	else {
		echo "No palindrome substring found!!";
		return false;
	}
}
